import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution542 {
    public int[][] updateMatrix(int[][] mat) {
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        int m=mat.length,n=mat[0].length;
        int[][] ans=new int[m][n];
        for (int[] an : ans) {
            Arrays.fill(an,Integer.MAX_VALUE);
        }
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (mat[i][j]==0){
                    ans[i][j]=0;
                    queue.add(new int[]{i,j});
                }
            }
        }
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            for (int i=0;i<4;i++){
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && ans[x][y]>ans[t[0]][t[1]]+1){
                    ans[x][y]=ans[t[0]][t[1]]+1;
                    queue.offer(new int[]{x,y});
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new Solution542().updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}})));
    }
}
